package pt.ipbeja.estig.eda;

public class HeapSort
{
   int[] array;
   int heapSize;
 /**
  * Heap Sort Constructor   
  * @param array Number list
  */
   public HeapSort( int[] array )
   {
      this.array = array;
      this.heapSize = array.length;
   }
   
//   private int parent( int i )
//   {
//      return ( int )( i / 2 );
//   }
   
   /**
    * Get left child node of a given node
    * @param i Node
    * @return Left child node
    */
   private int left( int i )
   {
      return 2 * i;
   }
   
   /**
    * Get right child node of a given node
    * @param i Node
    * @return Right child node
    */
   private int right( int i )
   {
      return ( 2 * i ) + 1;
   }
   /**
    * Heap Short Method 
    */
   public void sort()
   {
      this.build_MaxHeap();

      for( int i = this.array.length - 1; i > 0; i-- )
      {
         int aux = this.array[ 0 ];
         this.array[ 0 ] = this.array[ i ];
         this.array[ i ] = aux;
         this.heapSize--;
         this.max_heapify( 0 );
      }
//      System.out.println( this.array.length );
   }
   
   /**
    * Fix max-heap property
    * @param i Node
    */
   private void max_heapify( int i )
   {
      int largest;
      int l = this.left( i );
      int r = this.right( i );
      
      if( ( l < this.heapSize ) && ( this.array[ l ] > this.array[ i ] ) )
      {
         largest = l;
      }
      else
      {
         largest = i;
      }
      
      if( ( r < this.heapSize ) && ( this.array[ r ] > this.array[ largest ] ) )
      {
         largest = r;
      }
      
      if( largest != i )
      {
         int aux = this.array[ i ];
         this.array[ i ] = this.array[ largest ];
         this.array[ largest ] = aux;
         this.max_heapify( largest );
      }
   }
   
   /**
    * Heap builder from a data list
    */
   private void build_MaxHeap()
   {
      for( int i = ( int )( this.array.length / 2 ); i >= 0; i-- )
      {
         this.max_heapify( i );
      }
   }
}
